package leetcode.weekly.week307;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import leetcode.helper.tree.TreeNode;

//Solution3Test
public class Solution3 {

	Map<Integer, List<Integer>> edges;

	public int amountOfTime(TreeNode root, int start) {
		edges = new HashMap<>();
		this.build(root);
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		Set<Integer> infect = new HashSet<>();
		infect.add(start);
		int ans = -1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				List<Integer> nexts = edges.getOrDefault(cur, new ArrayList<>());
				for (int i = 0; i < nexts.size(); i++) {
					int next = nexts.get(i);
					if (!infect.contains(next)) {
						infect.add(next);
						queue.add(next);
					}
				}
				size--;
			}
			ans++;
		}
		return ans;
	}

	private void build(TreeNode root) {
		if (root == null) {
			return;
		}
		int cur = root.val;
		if (root.left != null) {
			int L = root.left.val;
			edges.computeIfAbsent(cur, key -> new ArrayList<>()).add(L);
			edges.computeIfAbsent(L, key -> new ArrayList<>()).add(cur);
			this.build(root.left);
		}
		if (root.right != null) {
			int R = root.right.val;
			edges.computeIfAbsent(cur, key -> new ArrayList<>()).add(R);
			edges.computeIfAbsent(R, key -> new ArrayList<>()).add(cur);
			this.build(root.right);
		}

	}

}
